package codingStudy.moocAlgorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author dell
 * @category LeetCode上数组相关算法题
 */
public class ArrayAlgorithm {

	/**
	 * 二分查找--迭代版本
	 * 
	 * @param arrys
	 *            查找的有序数组
	 * @param target
	 *            查找目标
	 * @return true：找到 false：未找到
	 */
	static boolean binarySearch(int[] arrys, int target) {
		int l = 0, r = arrys.length - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (arrys[mid] < target) {
				l = mid + 1;
			} else if (target < arrys[mid]) {
				r = mid - 1;
			} else {
				return true;
			}
		}
		return false;
	}

	/**
	 * 查找递归版
	 * 
	 * @param arrys
	 *            查找数组
	 * @param l
	 *            左下标
	 * @param r
	 *            右下标
	 * @param target
	 *            查找目标
	 * @return true：找到 false：未找到
	 */
	static boolean binarySearch(int[] arrys, int l, int r, int target) {

		if (l > r) {
			return false;
		}
		int mid = l + (r - l) / 2;
		if (arrys[mid] < target) {
			l = mid + 1;
			return binarySearch(arrys, l, r, target);
		} else if (target < arrys[mid]) {
			r = mid - 1;
			return binarySearch(arrys, l, r, target);
		}
		return true;

	}

	/**
	 * 利用双索引解决数组问题——27.去除重复元素
	 * 
	 * @param nums
	 *            代处理数组
	 * @param val
	 *            查找目标
	 * @return 剩余元素个数
	 */
	static int removeElement(int[] nums, int val) {
		int k = 0;
		int count = 0;
		int size = nums.length;
		/**
		 * 其中i指针用来寻找不是val的目标，k下标用来寻找val目标 实现方法： 当num[i]!=val时，i k 两个指针同时+1
		 * 当num[i]=val时，i+1，k则停止，
		 * 
		 */
		for (int i = 0; i < size; i++) {
			if (nums[i] != val) {
				if (i != k) {
					int t = nums[i];
					nums[i] = nums[k];
					nums[k] = t;
					k++;

				} else {
					k++;
				}
			} else {
				count++;
			}
		}
		return size - count;

	}

	/**
	 * 利用双索引解决数组问题——283.moves zeros
	 * 
	 * @param nums
	 *            代处理数组
	 * @param val
	 *            查找目标
	 * @return 剩余元素个数
	 */
	static void movesZeros(int[] nums) {

		int k = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != 0) {
				if (i != k) {
					int t = nums[i];
					nums[i] = nums[k];
					nums[k] = t;
					k++;
				} else {
					k++;
				}
			}
		}

	}

	/**
	 * 双索引——26.Remove Duplicated from Sorted Array
	 * 
	 * @param nums
	 *            待处理数组
	 * @return 去除重复后数组个数
	 */
	static int removeDuplicates(int[] nums) {

		int size = nums.length;
		int i = 0;
		for (int j = 1; j < nums.length; j++) {
			if (nums[j] != nums[i]) {
				i++;
				nums[i] = nums[j];
			}
		}
		for (int k = 0; k < size; k++) {
			System.out.println(nums[k]);
		}

		return i + 1;

	}

	/**
	 * 碰撞指针练习-167.TwoSumII
	 * 
	 * @param numbers
	 */
	static int[] colidePointer(int[] numbers, int target) {
		int size = numbers.length;
		int[] result = { 0, 0 };
		int i = 0;
		int j = size - 1;
		while (i <= j) {
			if (numbers[i] + numbers[j] < target) {
				i++;
			} else if (numbers[i] + numbers[j] == target) {
				result[0] = i;
				result[1] = j;
				return result;
			} else {
				j--;
			}
		}

		return null;

	}

	/**
	 * 碰撞指针——125.回文检测
	 * 
	 * @param s
	 * @return
	 */
	static boolean validPalidrome(String s) {
		char head, end;
		int size = s.length();
		int i = 0, j = size - 1;
		while (i <= j) {
			head = s.charAt(i);
			end = s.charAt(j);
			if (!Character.isLetterOrDigit(head))
				i++;
			else if (!Character.isLetterOrDigit(end)) {
				j--;
			} else {
				if (Character.toLowerCase(head) == Character.toLowerCase(end)) {
					i++;
					j--;
				} else {
					return false;
				}
			}
		}

		return true;

	}

	/**
	 * 碰撞指针——344翻转字符串
	 * 
	 * @param s
	 *            待翻转的字符串
	 * @return 返回翻转后字符串
	 */
	static String reverseString(String s) {
		char[] charArray = s.toCharArray();
		int i = 0, j = s.length() - 1;
		char temp;
		while (i <= j) {
			temp = charArray[i];
			charArray[i++] = charArray[j];
			charArray[j--] = temp;
		}
		return new String(charArray);

	}

	/**
	 * 碰撞指针——345.翻转元音字符串
	 * 
	 * @param s
	 *            待翻转的字符串
	 * @return 返回翻转后字符串
	 */
	static String reverseVowels(String s) {
		if (s.length() == 1)
			return s;
		boolean[] words = new boolean[256];
		words['a'] = true;
		words['e'] = true;
		words['i'] = true;
		words['o'] = true;
		words['u'] = true;
		words['A'] = true;
		words['E'] = true;
		words['I'] = true;
		words['O'] = true;
		words['U'] = true;
		char[] charArray = s.toCharArray();
		int i = 0, j = s.length() - 1;
		char temp;
		while (i <= j) {
			if (!words[charArray[i]])
				i++;
			if (!words[charArray[j]])
				j--;
			if (i < j && words[charArray[i]] && words[charArray[j]]) {
				temp = charArray[i];
				charArray[i++] = charArray[j];
				charArray[j--] = temp;
			}
		}
		return new String(charArray);

	}

	/**
	 * 碰撞指针——11. Container With Most Water
	 * 
	 * @param height
	 * @return 最大的容积
	 */
	static int maxArea(int[] height) {
		int hight = 0;
		int wide = 0;
		int maxArea = 0;
		int area = 0;
		int l = 0;
		int r = height.length - 1;
		while (l < r) {
			wide = r - l;
			if (height[l] < height[r]) {
				hight = height[l];
				l++;
			} else {
				hight = height[r];
				r--;
			}
			area = wide * hight;
			maxArea = Math.max(area, maxArea);
		}

		return maxArea;

	}

	/**
	 * 练习使用滑动窗口 209.Minimum Size Subarray Sum
	 * 
	 * @param s
	 * @param nums
	 * @return 最短子串的长度
	 */
	static int slidingWindow(int s, int[] nums) {
		int l = 0, r = -1;// 滑动窗口的范围是[l,r]
		int sum = 0;
		int res = nums.length + 1;// 设置最大的长度
		while (l < nums.length) {
			if (r + 1 < nums.length && sum < s) {
				sum += nums[++r];
			} else {
				sum -= nums[l++];
			}
			if (sum >= s)
				res = Math.min(res, r - l + 1);
		}
		if (res == nums.length + 1)
			return 0;

		return res;
	}

	/**
	 * 
	 * 滑动窗口：3 Longest SubstringRepeating Characters
	 * 
	 * @param s
	 * @return
	 */
	static int lengthOfLongSubstring(String s) {
		int l = 0;
		int r = 0;
		int length = s.length();
		int[] map = new int[256];
		int maxlength = 0;
		map[0] = 0;
		char key;
		while (l < length) {
			if (r < length && map[s.charAt(r)] < 1) {
				map[s.charAt(r)]++;
				maxlength = Math.max(maxlength, r - l + 1);
				r++;
			} else {
				key = s.charAt(l);
				map[key]--;
				l++;
			}
		}
		return maxlength;

	}

	/**
	 * 滑动窗口：438. Find All Anagrams in a String
	 * 
	 * @param s
	 * @param p
	 * @return
	 */
	static List<Integer> findAnagrams(String s, String p) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		List<Integer> list = new ArrayList<Integer>();
		int sLength = s.length();
		int pLength = p.length();
		initMap(map, p);
		int l = 0, r = 0;
		while (l < sLength && r < sLength) {
			Character key = s.charAt(r);
			if (map.containsKey(key)) {
				if (r - l + 1 == pLength && map.get(key) < 1) {
					map.put(key, 1);
					list.add(l);
					r++;
				}
				if (map.get(key) < 1) {
					map.put(key, 1);
					r++;
				} else {
					map.put(s.charAt(l), 0);
					l++;
				}
			} else {
				r++;
				l = r;
				initMap(map, p);
			}
		}

		return list;

	}

	static List<Integer> findAnagrams1(String s, String p) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		Map<Character, Integer> map1 = new HashMap<Character, Integer>();
		for (int i = 0; i < p.length(); i++) {
			char t = p.charAt(i);
			if (!map1.containsKey(t)) {
				map1.put(t, 1);
			} else {
				int value = map.get(t);
				map1.put(t, ++value);
			}
		}
		List<Integer> list = new ArrayList<Integer>();
		int sLength = s.length();
		int pLength = p.length();
		initMap(map, p);
		int l = 0, r = 0;
		while (l < sLength && r < sLength) {
			Character key = s.charAt(r);
			if (map.containsKey(key)) {
				int value = map.get(key) - 1;
				map.put(key, value);
				if (map.get(key) == 0) {
					if (r - l + 1 == pLength) {
						list.add(l);
						map.put(s.charAt(l), map1.get(s.charAt(l)));
						l++;
						r++;
					}
					r++;
				} else if (map.get(key) > 0) {
					r++;
				} else {
					r++;
					l = r;
					initMap(map, p);
				}
			} else {
				r++;
				l = r;
				initMap(map, p);
			}
		}

		return list;

	}

	static void initMap(Map<Character, Integer> map, String initString) {
		for (int i = 0; i < initString.length(); i++) {
			char t = initString.charAt(i);
			if (!map.containsKey(t)) {
				map.put(t, 1);
			} else {
				int value = map.get(t);
				map.put(t, ++value);
			}
		}
	}

	public static void main(String[] args) {
		int[] a = { 1, 2, 5, 3, 7 };

		// List<Integer> li = findAnagrams1("baaa", "aa");
		List<Integer> li = findAnagrams1("abab", "ab");

		for (Integer integer : li) {
			System.out.println(integer);
		}

		// System.out.println(reverseVowels("race a car"));
		// System.out.println(Character.toLowerCase('A'));
		// System.out.println(lengthOfLongSubstring("pwwwwkew"));

	}
}
